package org.lql.algo.codecrush.week010;

import org.lql.algo.common.TreeNode;

/**
 * @author: liangqinglong
 * @date: 2025-08-30 15:26
 * @description: LCR 155. 将二叉搜索树转化为排序的双向链表 <a href="https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/description/">...</a>
 **/
public class TreeToDoublyList {
	private TreeNode head = null; // 链表头
	private TreeNode prev = null; // 前驱指针

	public TreeNode treeToDoublyList(TreeNode root) {
		if (root == null) return null;

		inorder(root);

		// 收尾连接，变成循环双向链表
		head.left = prev;
		prev.right = head;

		return head;
	}

	private void inorder(TreeNode node) {
		if (node == null) return;

		inorder(node.left);

		if (prev == null) {
			head = node; // 第一个节点就是最小值
		} else {
			prev.right = node;
			node.left = prev;
		}
		prev = node; // 更新前驱

		inorder(node.right);
	}
}
